<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="theme-color" content="black"><meta name="author" content="李子康"><meta name="copyright" content="李子康"><meta name="generator" content="Hexo 4.2.1"><meta name="theme" content="hexo-theme-yun"><title>数据结构 第二讲 线性表 | Lizikang_Blog</title><link rel="stylesheet" href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@900&amp;display=swap" media="none" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/star-markdown-css@0.1.11/dist/yun/yun-markdown.min.css"><script src="//at.alicdn.com/t/font_1140697_stqaphw3j4.js" async></script><script src="https://cdn.jsdelivr.net/npm/scrollreveal/dist/scrollreveal.min.js" defer></script><script>document.addEventListener("DOMContentLoaded", () => {
  [".post-card",".post-content img"].forEach((target)=> {
    ScrollReveal().reveal(target);
  })
});
</script><script src="https://cdn.jsdelivr.net/npm/pjax@latest/pjax.min.js" defer></script><script src="/js/pjax.js" defer></script><link rel="shortcut icon" type="image/svg+xml" href="/images/%E7%9A%AE%E5%8D%A1%E4%B8%98-2.ico"><link rel="mask-icon" href="/images/%E7%9A%AE%E5%8D%A1%E4%B8%98-2.ico" color="black"><link rel="alternate icon" href="/yun.ico"><link rel="preload" href="/css/hexo-theme-yun.css" as="style"><link rel="preload" href="/js/utils.js" as="script"><link rel="preload" href="/js/hexo-theme-yun.js" as="script"><link rel="prefetch" href="/js/sidebar.js" as="script"><link rel="preconnect" href="https://cdn.jsdelivr.net" crossorigin><link rel="stylesheet" href="/css/hexo-theme-yun.css"><link rel="alternate" href="/atom.xml" title="Lizikang_Blog"><script id="yun-config">
    const Yun = window.Yun || {};
    window.CONFIG = {"root":"/","title":["Li","Zi","Kang","Blog"],"version":"0.9.2","anonymous_image":"https://cdn.jsdelivr.net/gh/YunYouJun/cdn/img/avatar/none.jpg","say":{"api":"https://v1.hitokoto.cn","hitokoto":true},"fireworks":{"colors":["102, 167, 221","62, 131, 225","33, 78, 194"]}};
  </script><script src="//at.alicdn.com/t/font_1929835_1z6thct9lfe.js" async></script><meta name="description" content="第二讲 线性表1. 将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。2. 对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。3. 线性表的分类(1) 数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；例如：数组(2) 数据元素在内存中分散存储，采用链式表">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构 第二讲 线性表">
<meta property="og:url" content="http://yoursite.com/2021/07/10/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/acwing/sjjg_2/index.html">
<meta property="og:site_name" content="Lizikang_Blog">
<meta property="og:description" content="第二讲 线性表1. 将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。2. 对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。3. 线性表的分类(1) 数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；例如：数组(2) 数据元素在内存中分散存储，采用链式表">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703145004164.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703211438769.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703145156452.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703211623904.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210705123934999.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703205443192.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703213333780.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703210247841.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703205625516.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210704125135359.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703210639180.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703210730300.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703205709442.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703205858599.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703214728201.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703215430852.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703215419546.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703220727048.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703220759353.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703210845455.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703210917316.png">
<meta property="article:published_time" content="2021-07-09T16:00:00.000Z">
<meta property="article:modified_time" content="2021-08-25T06:28:37.223Z">
<meta property="article:author" content="李子康">
<meta property="article:tag" content="数据结构">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703145004164.png"><script src="/js/ui/mode.js"></script><link rel="alternate" href="/atom.xml" title="Lizikang_Blog" type="application/atom+xml">
</head><body><script defer src="https://cdn.jsdelivr.net/npm/animejs@latest/anime.min.js"></script><script defer src="/js/ui/fireworks.js"></script><canvas class="fireworks"></canvas><div class="container"><a class="sidebar-toggle hty-icon-button" id="menu-btn"><div class="hamburger hamburger--spin" type="button"><span class="hamburger-box"><span class="hamburger-inner"></span></span></div></a><div class="sidebar-toggle sidebar-overlay"></div><aside class="sidebar"><script defer src="/js/sidebar.js"></script><ul class="sidebar-nav"><li class="sidebar-nav-item sidebar-nav-toc hty-icon-button sidebar-nav-active" data-target="post-toc-wrap" title="文章目录"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-list-ordered"></use></svg></li><li class="sidebar-nav-item sidebar-nav-overview hty-icon-button" data-target="site-overview-wrap" title="站点概览"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-passport-line"></use></svg></li></ul><div class="sidebar-panel" id="site-overview-wrap"><div class="site-info fix-top"><a class="site-author-avatar" href="/about/" title="李子康"><img width="96" loading="lazy" src="/images/bak.jpg" alt="李子康"></a><div class="site-author-name"><a href="/about/">李子康</a></div><a class="site-name" href="/about/site.html">Lizikang_Blog</a><sub class="site-subtitle"></sub><div class="site-desciption">个人技术博客</div></div><nav class="site-state"><a class="site-state-item hty-icon-button icon-home" href="/" title="我的主页"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-home-4-line"></use></svg></span></a><div class="site-state-item"><a href="/archives/" title="归档"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-archive-line"></use></svg></span><span class="site-state-item-count">27</span></a></div><div class="site-state-item"><a href="/categories/" title="分类"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-folder-2-line"></use></svg></span><span class="site-state-item-count">13</span></a></div><div class="site-state-item"><a href="/tags/" title="标签"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="site-state-item-count">9</span></a></div><a class="site-state-item hty-icon-button" href="https://yun.yunyoujun.cn" target="_blank" rel="noopener" title="文档"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-settings-line"></use></svg></span></a></nav><hr style="margin-bottom:0.5rem"><div class="links-of-author"><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://wpa.qq.com/msgrd?v=3&amp;uin=1191787635&amp;site=qq&amp;menu=yes" title="QQ" target="_blank" style="color:#12B7F5"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-qq-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://github.com/lizikanglzk" title="GitHub" target="_blank" style="color:#181717"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-github-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="mailto:1191787635@qq.com" title="E-Mail" target="_blank" style="color:#8E71C1"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-mail-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://gitee.com/li_zikang" title="gitee" target="_blank" style="color:#E6162D"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-gitee-copy"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://music.163.com/#/user/home?id=506556053" title="网易云音乐" target="_blank" style="color:#C10D0C"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-netease-cloud-music-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://blog.csdn.net/qq_43845915" title="csdn" target="_blank" style="color:#007722"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-csdn11"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://www.zhihu.com/people/zou-guo-lu-guo-bu-yao-cuo-guo-88" title="知乎" target="_blank" style="color:#0084FF"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-zhihu-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://space.bilibili.com/352594163" title="哔哩哔哩动画" target="_blank" style="color:#FF8EB3"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-bilibili-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="微信" target="_blank" style="color:#1AAD19"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-wechat-2-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="/atom.xml" title="RSS" target="_blank" style="color:orange"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-rss-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="/game1" title="Telegram Channel" target="_blank" style="color:#0088CC"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-youxi-copy-copy"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://travellings.now.sh/" title="Travelling" target="_blank" style="color:var(--hty-text-color)"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-send-plane-2-line"></use></svg></a></div><hr style="margin:0.5rem 1rem"><div class="links"><a class="links-item hty-icon-button" href="/links/" title="我的小伙伴们" style="color:dodgerblue"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-men-line"></use></svg></a><a class="links-item hty-icon-button" href="/girls/" title="我的老婆们" style="color:#FF8EB3"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-women-line"></use></svg></a></div><br><a class="links-item hty-icon-button" id="toggle-mode-btn" href="javascript:;" title="Mode" style="color: #f1cb64"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-contrast-2-line"></use></svg></a></div><div class="sidebar-panel sidebar-panel-active" id="post-toc-wrap"><div class="post-toc"><div class="post-toc-content"><ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#第二讲-线性表"><span class="toc-text">第二讲 线性表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1-将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。"><span class="toc-text">1. 将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2-对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。"><span class="toc-text">2. 对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#3-线性表的分类"><span class="toc-text">3. 线性表的分类</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#1-数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；"><span class="toc-text">(1) 数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#2-数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。"><span class="toc-text">(2) 数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度）"><span class="toc-text">4. 不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度）</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#1-数组：随机索引O-1-、插入O-n-、删除O-n"><span class="toc-text">(1) 数组：随机索引O(1)、插入O(n)、删除O(n)</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#2-单链表：查找某一元素O-n-、插入O-1-、删除O-n"><span class="toc-text">(2) 单链表：查找某一元素O(n)、插入O(1)、删除O(n)</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#3-双链表：查找某一元素O-n-、插入O-1-、删除O-1"><span class="toc-text">(3) 双链表：查找某一元素O(n)、插入O(1)、删除O(1)</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#5-考题：、2016-2、2012-42、2015-41、2019-41"><span class="toc-text">5. 考题：、2016-2、2012-42、2015-41、2019-41</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#6-押题：AcWing-34、AcWing-1451"><span class="toc-text">6. 押题：AcWing 34、AcWing 1451</span></a></li></ol></li></ol></div></div></div></aside><main class="sidebar-translate" id="content"><div id="post"><article class="post-block" itemscope itemtype="https://schema.org/Article"><link itemprop="mainEntityOfPage" href="http://yoursite.com/2021/07/10/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/acwing/sjjg_2/"><span hidden itemprop="author" itemscope itemtype="https://schema.org/Person"><meta itemprop="name" content="李子康"><meta itemprop="description"></span><span hidden itemprop="publisher" itemscope itemtype="https://schema.org/Organization"><meta itemprop="name" content="Lizikang_Blog"></span><header class="post-header"><h1 class="post-title" itemprop="name headline">数据结构 第二讲 线性表</h1><div class="post-meta"><div class="post-time" style="display:inline-block"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-calendar-line"></use></svg></span> <time title="创建时间：2021-07-10 00:00:00" itemprop="dateCreated datePublished" datetime="2021-07-10T00:00:00+08:00">2021-07-10</time><span class="post-meta-divider">-</span><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-calendar-2-line"></use></svg></span> <time title="修改时间：2021-08-25 14:28:37" itemprop="dateModified" datetime="2021-08-25T14:28:37+08:00">2021-08-25</time></div><span class="post-busuanzi"><span class="post-meta-divider">-</span><span class="post-meta-item-icon" title="阅读次数"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-eye-line"></use></svg> <span id="busuanzi_value_page_pv"></span></span></span><div class="post-classify"><span class="post-category"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-folder-line"></use></svg></span> <span itemprop="about" itemscope itemtype="https://schema.org/Thing"><a class="category" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="--text-color:var(--hty-text-color)" itemprop="url" rel="index"><span itemprop="text">数据结构</span></a></span> > <span itemprop="about" itemscope itemtype="https://schema.org/Thing"><a class="category" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/acwing/" style="--text-color:var(--hty-text-color)" itemprop="url" rel="index"><span itemprop="text">acwing</span></a></span></span><span class="post-tag"><span class="post-meta-divider">-</span><a class="tag" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="--text-color:var(--hty-text-color)"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="tag-name">数据结构</span></a></span></div></div></header><section class="post-body" itemprop="articleBody"><div class="post-content markdown-body" style="--smc-primary:black;"><h3 id="第二讲-线性表"><a href="#第二讲-线性表" class="headerlink" title="第二讲 线性表"></a>第二讲 线性表</h3><h4 id="1-将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。"><a href="#1-将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。" class="headerlink" title="1. 将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。"></a>1. 将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。</h4><h4 id="2-对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。"><a href="#2-对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。" class="headerlink" title="2. 对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。"></a>2. 对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。</h4><h4 id="3-线性表的分类"><a href="#3-线性表的分类" class="headerlink" title="3. 线性表的分类"></a>3. 线性表的分类</h4><h5 id="1-数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；"><a href="#1-数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；" class="headerlink" title="(1) 数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；"></a>(1) 数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；</h5><pre><code>例如：数组</code></pre><h5 id="2-数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。"><a href="#2-数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。" class="headerlink" title="(2) 数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。"></a>(2) 数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。</h5><pre><code>例如：单链表、双链表、循环单（双）链表</code></pre><h4 id="4-不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度）"><a href="#4-不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度）" class="headerlink" title="4. 不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度）"></a>4. 不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度）</h4><h5 id="1-数组：随机索引O-1-、插入O-n-、删除O-n"><a href="#1-数组：随机索引O-1-、插入O-n-、删除O-n" class="headerlink" title="(1) 数组：随机索引O(1)、插入O(n)、删除O(n)"></a>(1) 数组：随机索引O(1)、插入O(n)、删除O(n)</h5><h5 id="2-单链表：查找某一元素O-n-、插入O-1-、删除O-n"><a href="#2-单链表：查找某一元素O-n-、插入O-1-、删除O-n" class="headerlink" title="(2) 单链表：查找某一元素O(n)、插入O(1)、删除O(n)"></a>(2) 单链表：查找某一元素O(n)、插入O(1)、删除O(n)</h5><h5 id="3-双链表：查找某一元素O-n-、插入O-1-、删除O-1"><a href="#3-双链表：查找某一元素O-n-、插入O-1-、删除O-1" class="headerlink" title="(3) 双链表：查找某一元素O(n)、插入O(1)、删除O(1)"></a>(3) 双链表：查找某一元素O(n)、插入O(1)、删除O(1)</h5><h4 id="5-考题：、2016-2、2012-42、2015-41、2019-41"><a href="#5-考题：、2016-2、2012-42、2015-41、2019-41" class="headerlink" title="5. 考题：、2016-2、2012-42、2015-41、2019-41"></a>5. 考题：、2016-2、2012-42、2015-41、2019-41</h4><p><strong>2016-1</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703145004164.png" alt="image-20210703145004164" loading="lazy"></p>
<blockquote>
<p>c   a   e  b  d   NULL  </p>
<p>​        f</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703211438769.png" alt="image-20210703211438769" loading="lazy"></p>
</blockquote>
<p><strong>2016-2</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703145156452.png" alt="image-20210703145156452" loading="lazy"></p>
<blockquote>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703211623904.png" alt="image-20210703211623904" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210705123934999.png" alt="image-20210705123934999" loading="lazy"></p>
</blockquote>
<p><strong>2012-42</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703205443192.png" alt="image-20210703205443192" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703213333780.png" alt="image-20210703213333780" loading="lazy"></p>
<blockquote>
<p><a href="https://www.acwing.com/problem/content/62/" target="_blank" rel="noopener">acwing 66 两个链表的第一个公共结点</a></p>
<p><strong>c++:</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-comment">/**</span><br><span class="hljs-comment">* Definition for singly-linked list.</span><br><span class="hljs-comment">* struct ListNode &#123;</span><br><span class="hljs-comment">*     int val;</span><br><span class="hljs-comment">*     ListNode *next;</span><br><span class="hljs-comment">*     ListNode(int x) : val(x), next(NULL) &#123;&#125;</span><br><span class="hljs-comment">* &#125;;</span><br><span class="hljs-comment">*/</span><br><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> &#123;</span><br><span class="hljs-keyword">public</span>:<br>   <span class="hljs-function">ListNode *<span class="hljs-title">findFirstCommonNode</span><span class="hljs-params">(ListNode *headA, ListNode *headB)</span> </span>&#123;<br>       <span class="hljs-keyword">auto</span> p = headA;<br>       <span class="hljs-keyword">auto</span> q = headB;<br>       <span class="hljs-keyword">while</span>(p!=q)&#123;<br>           <span class="hljs-keyword">if</span>(p)<br>           p = p-&gt;next;<br>           <span class="hljs-keyword">else</span> p = headB;<br>           <span class="hljs-keyword">if</span>(q)<br>           q = q-&gt;next;<br>           <span class="hljs-keyword">else</span> q = headA;<br>       &#125;<br>       <span class="hljs-keyword">return</span> p;<br>   &#125;<br>&#125;;<br></code></pre></td></tr></table></figure>
</blockquote>
<blockquote>
<p><strong>c:</strong></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><code class="hljs c">&gt;<span class="hljs-comment">/**</span><br><span class="hljs-comment">* Definition for singly-linked list.</span><br><span class="hljs-comment">* struct ListNode &#123;</span><br><span class="hljs-comment">*     int val;</span><br><span class="hljs-comment">*     struct ListNode *next;</span><br><span class="hljs-comment">* &#125;;</span><br><span class="hljs-comment">*/</span><br>&gt;<span class="hljs-function">struct ListNode *<span class="hljs-title">findFirstCommonNode</span><span class="hljs-params">(struct ListNode *headA, struct ListNode *headB)</span> </span>&#123;<br>   <br>   <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">ListNode</span> *<span class="hljs-title">p</span> = <span class="hljs-title">headA</span>;</span><br>   <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">ListNode</span> *<span class="hljs-title">q</span> = <span class="hljs-title">headB</span>;</span><br>   <br>   <span class="hljs-keyword">while</span>(p!=q)&#123;<br>       <br>       <span class="hljs-keyword">if</span>(p)&#123;<br>           p= p-&gt;next;<br>           <br>       &#125;<span class="hljs-keyword">else</span> p = headB;<br>       <br>        <span class="hljs-keyword">if</span>(q)&#123;<br>           q= q-&gt;next;<br>           <br>       &#125;<span class="hljs-keyword">else</span> q = headA;<br>       <br>   &#125;<br>   <br>   <span class="hljs-keyword">return</span> p;<br>   <br>&gt;&#125;<br></code></pre></td></tr></table></figure>


</blockquote>
<blockquote>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703210247841.png" alt="image-20210703210247841" loading="lazy"></p>
</blockquote>
<p><strong>2015-41</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703205625516.png" alt="image-20210703205625516" loading="lazy"></p>
<p><strong>删除节点</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210704125135359.png" alt="image-20210704125135359" loading="lazy"></p>
<blockquote>
<p><a href="https://www.acwing.com/problem/content/3759/" target="_blank" rel="noopener">acwing 3756. 筛选链表</a>  </p>
<p><strong>c++:</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><code class="hljs c++">&gt;<span class="hljs-comment">/**</span><br><span class="hljs-comment">&gt;* Definition for singly-linked list.</span><br><span class="hljs-comment">&gt;* struct ListNode &#123;</span><br><span class="hljs-comment">&gt;*     int val;</span><br><span class="hljs-comment">&gt;*     ListNode *next;</span><br><span class="hljs-comment">&gt;*     ListNode(int x) : val(x), next(NULL) &#123;&#125;</span><br><span class="hljs-comment">&gt;* &#125;;</span><br><span class="hljs-comment">&gt;*/</span><br>&gt;<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> &#123;</span><br>&gt;<span class="hljs-keyword">public</span>:<br>  <span class="hljs-function">ListNode* <span class="hljs-title">filterList</span><span class="hljs-params">(ListNode* head)</span> </span>&#123;<br>      <span class="hljs-keyword">bool</span> stu[<span class="hljs-number">10000</span>+<span class="hljs-number">5</span>]=&#123;<span class="hljs-literal">false</span>&#125;;<br>      stu[<span class="hljs-built_in">abs</span>(head-&gt;val)] = <span class="hljs-literal">true</span>;<br>      <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> p = head; p-&gt;next ;)&#123;<br><br>          <span class="hljs-keyword">auto</span> t = <span class="hljs-built_in">abs</span>(p-&gt;next-&gt;val);<br>          <span class="hljs-keyword">if</span>(stu[t])&#123;<br>              <span class="hljs-comment">// 已经存在，删除</span><br>              <span class="hljs-keyword">auto</span> q  = p-&gt;next;<br>              p-&gt;next = q-&gt;next;<br>              <span class="hljs-keyword">delete</span> q;<br><br><br>          &#125;<span class="hljs-keyword">else</span>&#123;<br>              <span class="hljs-comment">// 不存在，</span><br>              stu[t] = <span class="hljs-literal">true</span>;<br>              p = p-&gt;next;<br><br><br>          &#125;<br><br>      &#125;<br><br>      <span class="hljs-keyword">return</span> head;<br>  &#125;<br>&gt;&#125;;<br></code></pre></td></tr></table></figure>
</blockquote>
<blockquote>
<p><strong>c:</strong></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><code class="hljs c">&gt;<span class="hljs-comment">/**</span><br><span class="hljs-comment">* Definition for singly-linked list.</span><br><span class="hljs-comment">* struct ListNode &#123;</span><br><span class="hljs-comment">*     int val;</span><br><span class="hljs-comment">*     struct ListNode *next;</span><br><span class="hljs-comment">* &#125;;</span><br><span class="hljs-comment">* </span><br><span class="hljs-comment">* Note: The returned array must be malloced, assume caller calls free().</span><br><span class="hljs-comment">*/</span><br>&gt;<span class="hljs-function">struct ListNode* <span class="hljs-title">filterList</span><span class="hljs-params">(struct ListNode* head)</span> </span>&#123;<br>   <br>   <span class="hljs-keyword">bool</span> stu[<span class="hljs-number">10000</span>+<span class="hljs-number">5</span>] = &#123;<span class="hljs-literal">false</span>&#125;;  <span class="hljs-comment">//记录节点中的值是否被使用了</span><br>   <br>   stu[<span class="hljs-built_in">abs</span>(head-&gt;val)] = <span class="hljs-literal">true</span>;   <span class="hljs-comment">// 第一个节点的值使用后  </span><br>   <br>   <span class="hljs-keyword">for</span>(struct ListNode *p = head ; p-&gt;next ;)&#123;<br>       <br>       <span class="hljs-keyword">int</span> x = <span class="hljs-built_in">abs</span>( p-&gt;next-&gt;val );<br>       <br>       <span class="hljs-keyword">if</span>(stu[ x ] ) <span class="hljs-comment">// 判断此时节点的值是否被使用</span><br>       &#123;<br>           <span class="hljs-comment">// 已经存在，使用过 删除值一样的结点</span><br>           <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">ListNode</span> *<span class="hljs-title">q</span> = <span class="hljs-title">p</span>-&gt;<span class="hljs-title">next</span>;</span><br>           p-&gt;next = q-&gt;next;<br>           <span class="hljs-built_in">free</span>(q);<br>           <br>       &#125;<span class="hljs-keyword">else</span>&#123;<br>           <span class="hljs-comment">// 此时节点的值第一次出现，现在标记使用</span><br>           stu[x] = <span class="hljs-literal">true</span>;<br>           p=p-&gt;next ; <span class="hljs-comment">// 到下一个结点；</span><br>           <br>           <br>       &#125;<br>       <br>       <br>   &#125;<br>   <br>   <span class="hljs-keyword">return</span> head;<br>&gt;&#125;<br></code></pre></td></tr></table></figure>


</blockquote>
<blockquote>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703210639180.png" alt="image-20210703210639180" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703210730300.png" alt="image-20210703210730300" loading="lazy"></p>
</blockquote>
<p><strong>2019-41</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703205709442.png" alt="image-20210703205709442" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703205858599.png" alt="image-20210703205858599" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703214728201.png" alt="image-20210703214728201" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703215430852.png" alt="image-20210703215430852" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703215419546.png" alt="image-20210703215419546" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703220727048.png" alt="image-20210703220727048" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703220759353.png" alt="q" loading="lazy"></p>
<p><a href="https://www.acwing.com/problem/content/3760/" target="_blank" rel="noopener">acwing 3757. 重排链表</a></p>
<p><strong>c++:</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * Definition for singly-linked list.</span><br><span class="hljs-comment"> * struct ListNode &#123;</span><br><span class="hljs-comment"> *     int val;</span><br><span class="hljs-comment"> *     ListNode *next;</span><br><span class="hljs-comment"> *     ListNode(int x) : val(x), next(NULL) &#123;&#125;</span><br><span class="hljs-comment"> * &#125;;</span><br><span class="hljs-comment"> */</span><br><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> &#123;</span><br><span class="hljs-keyword">public</span>:<br>    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">rearrangedList</span><span class="hljs-params">(ListNode* head)</span> </span>&#123;<br>        <span class="hljs-comment">// 如果链表只有一个元素 , 不用处理直接打印</span><br>       <span class="hljs-keyword">if</span>(head-&gt;next == <span class="hljs-literal">NULL</span>) <span class="hljs-keyword">return</span> ; <br>        <br>        <span class="hljs-comment">// 链表长度</span><br>        <br>        <span class="hljs-keyword">int</span> n = <span class="hljs-number">0</span>;<br>        <br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> t = head;t;t =t-&gt;next)&#123;<br>            <span class="hljs-comment">// cout&lt;&lt;head-&gt;val;</span><br>            n++;<br>        &#125;<br>      <br>        <span class="hljs-comment">// cout&lt;&lt;n&lt;&lt;endl;</span><br>        <br>        <span class="hljs-comment">// 前半段的结点数， 链表分为2段 1~mid-1 , mid ~ n;</span><br>        <span class="hljs-keyword">int</span> mid  = (n+<span class="hljs-number">1</span>)/<span class="hljs-number">2</span>;<br>        <span class="hljs-keyword">auto</span> a  = head;<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;mid<span class="hljs-number">-1</span>;i++)a=a-&gt;next;<br>        <br>        <span class="hljs-keyword">auto</span> b =a-&gt;next;<br>        <span class="hljs-keyword">auto</span> c = b -&gt;next;<br>        <br>        a-&gt;next = <span class="hljs-literal">NULL</span>;<br>        b-&gt;next = <span class="hljs-literal">NULL</span>;<br>        <br>        <span class="hljs-comment">// 翻转 mid ~ n  到n~mid;</span><br>        <span class="hljs-keyword">while</span>(c)&#123;<br>            <br>            <span class="hljs-comment">// 预存后面的节点地址</span><br>            <span class="hljs-keyword">auto</span> t  = c-&gt;next;<br>            c-&gt;next = b; <span class="hljs-comment">// 翻转</span><br>            <br>            <span class="hljs-comment">//b,c 后移一位</span><br>            b = c;<br>            c = t;<br>            <br>        &#125;<br>        <span class="hljs-comment">// 1~mid-1与 n ~ mid 合并      b此时已经到最后一个节点，c是NULL</span><br>        <br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> p = head, q= b; q; )&#123;<br>            <br>            <span class="hljs-comment">// 预存q-&gt;next 的节点</span><br>            <span class="hljs-keyword">auto</span> t = q-&gt;next ;<br>            <br>            <span class="hljs-comment">//p与q连接</span><br>            q-&gt;next = p-&gt;next;<br>            p-&gt;next = q;<br>            <br>            <br>            <span class="hljs-comment">// p,q 后移</span><br>            p = q-&gt;next; <span class="hljs-comment">// or p=p-&gt;next-&gt;next  此时这里 p-&gt;next就是q</span><br>            q= t  ;  <span class="hljs-comment">// q 到之前预存的t的位置</span><br>            <br>            <span class="hljs-comment">//循环实现，达到合并</span><br>        &#125;<br>        <br>       <br>        <span class="hljs-keyword">return</span>;<br>    &#125;<br>&#125;;<br></code></pre></td></tr></table></figure>

<p><strong>c:</strong></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br></pre></td><td class="code"><pre><code class="hljs c"><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * Definition for singly-linked list.</span><br><span class="hljs-comment"> * struct ListNode &#123;</span><br><span class="hljs-comment"> *     int val;</span><br><span class="hljs-comment"> *     struct ListNode *next;</span><br><span class="hljs-comment"> * &#125;;</span><br><span class="hljs-comment"> */</span><br><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">rearrangedList</span><span class="hljs-params">(struct ListNode* head)</span> </span>&#123;<br>    <br>      <span class="hljs-comment">// 如果链表只有一个元素 , 不用处理直接打印</span><br>       <span class="hljs-keyword">if</span>(head-&gt;next == <span class="hljs-literal">NULL</span>) <span class="hljs-keyword">return</span> ; <br>        <br>        <span class="hljs-comment">// 链表长度</span><br>        <br>        <span class="hljs-keyword">int</span> n = <span class="hljs-number">0</span>;<br>        <br>        <span class="hljs-keyword">for</span>(struct ListNode* t = head;t;t =t-&gt;next)&#123;<br>            <span class="hljs-comment">// cout&lt;&lt;head-&gt;val;</span><br>            n++;<br>        &#125;<br>      <br>        <span class="hljs-comment">// cout&lt;&lt;n&lt;&lt;endl;</span><br>        <br>        <span class="hljs-comment">// 前半段的结点数， 链表分为2段 1~mid-1 , mid ~ n;</span><br>        <span class="hljs-keyword">int</span> mid  = (n+<span class="hljs-number">1</span>)/<span class="hljs-number">2</span>;<br>        <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">ListNode</span>* <span class="hljs-title">a</span>  = <span class="hljs-title">head</span>;</span><br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;mid<span class="hljs-number">-1</span>;i++)a=a-&gt;next;<br>        <br>        <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">ListNode</span>* <span class="hljs-title">b</span> =<span class="hljs-title">a</span>-&gt;<span class="hljs-title">next</span>;</span><br>        <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">ListNode</span>* <span class="hljs-title">c</span> = <span class="hljs-title">b</span> -&gt;<span class="hljs-title">next</span>;</span><br>        <br>        a-&gt;next = <span class="hljs-literal">NULL</span>;<br>        b-&gt;next = <span class="hljs-literal">NULL</span>;<br>        <br>        <span class="hljs-comment">// 翻转 mid ~ n  到n~mid;</span><br>        <span class="hljs-keyword">while</span>(c)&#123;<br>            <br>            <span class="hljs-comment">// 预存后面的节点地址</span><br>            <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">ListNode</span>* <span class="hljs-title">t</span>  = <span class="hljs-title">c</span>-&gt;<span class="hljs-title">next</span>;</span><br>            c-&gt;next = b; <span class="hljs-comment">// 翻转</span><br>            <br>            <span class="hljs-comment">//b,c 后移一位</span><br>            b = c;<br>            c = t;<br>            <br>        &#125;<br>        <span class="hljs-comment">// 1~mid-1与 n ~ mid 合并      b此时已经到最后一个节点，c是NULL</span><br>        <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">ListNode</span>* <span class="hljs-title">q</span>= <span class="hljs-title">b</span>;</span><br>        <span class="hljs-keyword">for</span>(struct ListNode* p = head; q; )&#123;<br>            <br>            <span class="hljs-comment">// 预存q-&gt;next 的节点</span><br>            <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">ListNode</span>* <span class="hljs-title">t</span> = <span class="hljs-title">q</span>-&gt;<span class="hljs-title">next</span> ;</span><br>            <br>            <span class="hljs-comment">//p与q连接</span><br>            q-&gt;next = p-&gt;next;<br>            p-&gt;next = q;<br>            <br>            <br>            <span class="hljs-comment">// p,q 后移</span><br>            p = q-&gt;next; <span class="hljs-comment">// or p=p-&gt;next-&gt;next  此时这里 p-&gt;next就是q</span><br>            q= t  ;  <span class="hljs-comment">// q 到之前预存的t的位置</span><br>            <br>            <span class="hljs-comment">//循环实现，达到合并</span><br>        &#125;<br>        <br>       <br>        <span class="hljs-keyword">return</span>;<br>    <br>    <br>&#125;<br></code></pre></td></tr></table></figure>



<blockquote>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703210845455.png" alt="image-20210703210845455" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210703210917316.png" alt="image-20210703210917316" loading="lazy"></p>
</blockquote>
<h4 id="6-押题：AcWing-34、AcWing-1451"><a href="#6-押题：AcWing-34、AcWing-1451" class="headerlink" title="6. 押题：AcWing 34、AcWing 1451"></a>6. 押题：AcWing 34、AcWing 1451</h4><p><a href="https://www.acwing.com/problem/content/86/" target="_blank" rel="noopener"><strong>AcWing 34</strong></a></p>
<p><strong><a href="https://www.acwing.com/problem/content/1453/" target="_blank" rel="noopener">AcWing 1451</a></strong></p>
</div></section></article><div class="post-nav"><div class="post-nav-item"><a class="post-nav-prev" href="/2021/07/11/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/acwing/sjjg_3/" rel="prev" title="数据结构 第三讲 栈与队列"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-left-s-line"></use></svg><span class="post-nav-text">数据结构 第三讲 栈与队列</span></a></div><div class="post-nav-item"><a class="post-nav-next" href="/2021/07/03/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/acwing/sjjg_1/" rel="next" title="数据结构 第一讲 时间复杂度、特殊矩阵的存储和压缩"><span class="post-nav-text">数据结构 第一讲 时间复杂度、特殊矩阵的存储和压缩</span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-right-s-line"></use></svg></a></div></div></div><div id="comment"><div class="comment-tooltip text-center"></div><div id="valine-container"></div><script src="https://cdn.jsdelivr.net/npm/valine@latest/dist/Valine.min.js"></script><script>function initValine() {
  const valineConfig = {"enable":true,"appId":"q22e7srtjevOqYmzusWCYIru-gzGzoHsz","appKey":"PMyzTxHUFQ77nPj1IWMcMDK3","placeholder":"畅所欲言！","avatar":null,"meta":["nick","mail","link"],"pageSize":10,"visitor":false,"highlight":true,"recordIP":false,"enableQQ":true,"el":"#valine-container","lang":"zh-cn"}
  valineConfig.path = window.location.pathname
  new Valine(valineConfig)
}
setTimeout(initValine, 1000)</script></div></main><footer class="sidebar-translate" id="footer"><div class="copyright"><span>&copy; 2020 – 2022 </span><span class="with-love" id="animate"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-cloud-line"></use></svg></span><span class="author"> 李子康</span></div><div class="powered"><span>由 <a href="https://hexo.io" target="_blank" rel="noopener">Hexo</a> 驱动 v4.2.1</span><span class="footer-separator">|</span><span>主题 - <a rel="noopener" href="https://github.com/YunYouJun/hexo-theme-yun" target="_blank"><span>Yun</span></a> v0.9.2</span></div><div class="live_time"><span>本博客已萌萌哒地运行</span><span id="display_live_time"></span><span class="moe-text">(●'◡'●)</span><script>function blog_live_time() {
  window.setTimeout(blog_live_time, 1000);
  const start = new Date('2020-07-05T00:00:00');
  const now = new Date();
  const timeDiff = (now.getTime() - start.getTime());
  const msPerMinute = 60 * 1000;
  const msPerHour = 60 * msPerMinute;
  const msPerDay = 24 * msPerHour;
  const passDay = Math.floor(timeDiff / msPerDay);
  const passHour = Math.floor((timeDiff % msPerDay) / 60 / 60 / 1000);
  const passMinute = Math.floor((timeDiff % msPerHour) / 60 / 1000);
  const passSecond = Math.floor((timeDiff % msPerMinute) / 1000);
  display_live_time.innerHTML = " " + passDay + " 天 " + passHour + " 小时 " + passMinute + " 分 " + passSecond + " 秒";
}
blog_live_time();
</script></div><div id="busuanzi"><script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><span id="busuanzi_container_site_uv" title="总访客量"><span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-user-line"></use></svg></span><span id="busuanzi_value_site_uv"></span></span><span class="footer-separator">|</span><span id="busuanzi_container_site_pv" title="总访问量"><span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-eye-line"></use></svg></span><span id="busuanzi_value_site_pv"></span></span></div></footer><a class="hty-icon-button" id="goUp" aria-label="back-to-top" href="#"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-up-s-line"></use></svg><svg class="progress-circle-container" viewBox="0 0 100 100"><circle class="progress-circle" id="progressCircle" cx="50" cy="50" r="48" fill="none" stroke="black" stroke-width="2" stroke-linecap="round"></circle></svg></a></div><script defer src="/js/utils.js"></script><script defer src="/js/hexo-theme-yun.js"></script><script defer src="/js/player.js"></script></body></html>